﻿//-----------------------------------------------------------------------
// <copyright file="Graph.cs" company="Luboš Bretschnieder">
// Copyright (c) 2008 Luboš Bretschnieder, Licensed under the Apache License, Version 2.0.
// </copyright>
//-----------------------------------------------------------------------
namespace Graphs
{
    using System;
    using System.Collections.Generic;

    /// <summary>
    /// Graph implementation.
    /// </summary>
    public class Graph : ICloneable
    {
        /// <summary>Alphabetically sorted list of vertices</summary>
        private IList<Vertex> vertices;

        /// <summary>Alphabetically sorted list of sorted vertices</summary>
        private SortedList<string, Vertex> sortedVertices;

        /// <summary>List of edges.</summary>
        private List<Edge> edges;

        /// <summary>
        /// Initializes a new instance of the <see cref="Graph"/> class.
        /// </summary>
        public Graph()
        {
            this.vertices = new List<Vertex>();
            this.sortedVertices = new SortedList<string, Vertex>();
            this.edges = new List<Edge>();
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Graph"/> class.
        /// </summary>
        /// <param name="vertices">The vertices.</param>
        /// <param name="edges">The edges.</param>
        public Graph(List<Vertex> vertices, List<Edge> edges)
        {
            this.vertices = vertices;
            this.edges = edges;
        }

        /// <summary>
        /// Gets or sets the vertices.
        /// </summary>
        /// <value>The vertices.</value>
        public IList<Vertex> Vertices
        {
            get { return this.vertices; }
            set { this.vertices = value; }
        }

        /// <summary>
        /// Gets or sets the sorted vertices.
        /// </summary>
        /// <value>The sorted vertices.</value>
        public SortedList<string, Vertex> SortedVertices
        {
            get { return this.sortedVertices; }
            set { this.sortedVertices = value; }
        }

        /// <summary>
        /// Gets or sets the edges.
        /// </summary>
        /// <value>The edges.</value>
        public List<Edge> Edges
        {
            get { return this.edges; }
            set { this.edges = value; }
        }

        /// <summary>
        /// Gets the vertex.
        /// </summary>
        /// <param name="name">The vertex name.</param>
        /// <returns>The vertex.</returns>
        public Vertex GetVertex(string name)
        {
            foreach (Vertex vertex in this.sortedVertices.Values)
            {
                if (vertex.Name.Equals(name))
                {
                    return vertex;
                }
            }

            return null;
        }

        /// <summary>
        /// Gets the edge between vertices.
        /// </summary>
        /// <param name="vertex1">The vertex on one side of egde.</param>
        /// <param name="vertex2">The vertex on the other side of edge.</param>
        /// <returns>The edge between two supplied vertices.</returns>
        public Edge GetEdge(Vertex vertex1, Vertex vertex2)
        {
            foreach (Edge edge in this.edges)
            {
                if ((edge.From == vertex1 && edge.To == vertex2) || (edge.From == vertex2 && edge.To == vertex1))
                {
                    return edge;
                }
            }

            return null;
        }

        /// <summary>
        /// Finds the connected vertices.
        /// </summary>
        /// <param name="vertex">The vertex.</param>
        /// <param name="processedEdges">Processed edges.</param>
        /// <returns>The connected vertices.</returns>
        public List<Vertex> FindConnectedVertices(Vertex vertex, List<Edge> processedEdges)
        {
            List<Vertex> connectedVertices = new List<Vertex>();

            foreach (Edge edge in this.edges)
            {
                if (!processedEdges.Contains(edge))
                {
                    if (edge.From.Equals(vertex))
                    {
                        connectedVertices.Add(edge.To);
                    }
                    else if (edge.To.Equals(vertex))
                    {
                        connectedVertices.Add(edge.From);
                    }
                }
            }

            return connectedVertices;
        }

        /// <summary>
        /// Creates a new object that is a copy of the current instance.
        /// </summary>
        /// <returns>
        /// A new object that is a copy of this instance.
        /// </returns>
        object ICloneable.Clone()
        {
            return this.Clone();
        }

        /// <summary>
        /// Clones this instance.
        /// </summary>
        /// <returns>Cloned graph.</returns>
        public virtual Graph Clone()
        {
            Graph graph = (Graph)MemberwiseClone();

            graph.Vertices = new List<Vertex>();
            graph.SortedVertices = new SortedList<string, Vertex>();
            foreach (Vertex vertex in this.vertices)
            {
                Vertex clonedVertex = vertex.Clone();
                graph.vertices.Add(clonedVertex);
                graph.sortedVertices.Add(clonedVertex.Name, clonedVertex);
            }

            graph.Edges = new List<Edge>();
            foreach (Edge edge in this.edges)
            {
                Edge edgeClone = edge.Clone();
                edgeClone.From = graph.GetVertex(edge.From.Name);
                edgeClone.To = graph.GetVertex(edge.To.Name);

                graph.Edges.Add(edgeClone);
            }

            return graph;
        }
    }
}